package com.gjx.leetcode;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;
//144. 二叉树的前序遍历
//
//给定一个二叉树，返回它的 前序 遍历。
//
// 示例:
//
//输入: [1,null,2,3]  
//   1
//    \
//     2
//    /
//   3 
//
//输出: [1,2,3]
//进阶: 递归算法很简单，你可以通过迭代算法完成吗？
//



public class Solution144 {
	public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        if (root == null) {
        	return res;
        }
        
        Stack<TreeNode> stack = new Stack<>();
        stack.push(root);
        
        while (!stack.isEmpty()) {
        	
        	TreeNode tn = stack.pop();
        	
        	res.add(tn.val);
        	
        	if (tn.right != null) {
        		stack.push(tn.right);
        	}
        	
        	if (tn.left != null) {
        		stack.push(tn.left);
        	}
        	
        }
        
        return res;
    }
}
